//原文链接：
//https://blog.csdn.net/ITSOK_123/article/details/124526013
//递归（O(N),O(N)）
void preTraversal(TreeNode *root,vector<int>& vec){
        if(root == nullptr) return;
        vec.push_back(root->val);
        preTraversal(root->left,vec);
        preTraversal(root->right,vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> pvec;
        if(root == nullptr) return;
        pvec.push_back(root->val);
        
    }

//迭代实现递归（O(N),O(N)）
vector<int> preorderTraversal(TreeNode* root) {
        // 定义返回结果向量以及遍历工作栈
        vector<int> pvec;
        stack<TreeNode*>st;
        //根节点为空，则直接返回
        if(root == nullptr) return pvec;
        st.push(root);
        // 栈不为空，则说明有未处理的节点
        while(!st.empty()){
            // 输出当前根结点的值
            TreeNode* node = st.top();
            st.pop();
            pvec.push_back(node->val);
            // 根节点有右子树则右子树根节点入栈
            if(node->right) st.push(node->right);
            // 根节点有左子树则左子树根节点入栈
            if(node->left) st.push(node->left);
        }
        return pvec;
    }

//迭代法（O(N),O(N)）
vector<int> preorderTraversal(TreeNode* root) {
        // 定义返回结果向量以及遍历工作栈
        vector<int> pvec;
        stack<TreeNode*>st;
        //根节点为空，则直接返回
        if(root == nullptr) return pvec;
        // 工作节点
        TreeNode* node = root;
        while(!st.empty() || node){
            //沿着根节点的左分支一直下沉
            while(node){
                st.push(node);
                pvec.push_back(node->val);
                node = node->left;
            }
            //当前节点再没有左子树，处理其右子树
            TreeNode* cur = st.top();
            st.pop();
            node = cur->right;
        }
        return pvec;
    }
